//Write a function to find the longest common prefix string amongst an array of 
//strings. 
//
// If there is no common prefix, return an empty string "". 
//
// 
// Example 1: 
//
// 
//Input: strs = ["flower","flow","flight"]
//Output: "fl"
// 
//
// Example 2: 
//
// 
//Input: strs = ["dog","racecar","car"]
//Output: ""
//Explanation: There is no common prefix among the input strings.
// 
//
// 
// Constraints: 
//
// 
// 1 <= strs.length <= 200 
// 0 <= strs[i].length <= 200 
// strs[i] consists of only lower-case English letters. 
// 
// Related Topics 字符串 
// 👍 1592 👎 0


package leetcode.editor.cn;

//Java：Longest Common Prefix
class P14LongestCommonPrefix {
    public static void main(String[] args) {
        Solution solution = new P14LongestCommonPrefix().new Solution();
        // TO TEST
        System.out.println(solution.longestCommonPrefix(new String[]{"flower","flow","flight"}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        //1.纵向
        public String longestCommonPrefixPre(String[] strs) {
            StringBuilder sb = new StringBuilder();
            int index = 0;
            boolean has = true;
            while (index < strs[0].length() && has) {
                sb.append(strs[0].charAt(index));
                for (int i = 0; i < strs.length; i++) {
                    String str = strs[i];
                    if (!str.startsWith(sb.toString())) {
                        has = false;
                        sb.replace(sb.length() - 1, sb.length(), "");
                        break;
                    }
                }
                index++;

            }
            return sb.toString();
        }
        //2.横向
        public String longestCommonPrefixSub(String[] strs) {
            for (int i = 0; i < strs.length - 1; i++) {
                String cur = strs[i];
                String next = strs[i + 1];
                int end = 1;
                while (end <= next.length() && cur.startsWith(next.substring(0, end))) {
                    end++;
                }
                strs[i + 1] = next.substring(0, end - 1);
            }
            return strs[strs.length - 1];
        }

        public String longestCommonPrefix(String[] strs) {
            if (strs == null || strs.length == 0) {
                return "";
            } else {
                return longestCommonPrefix(strs, 0, strs.length - 1);
            }
        }
        //3.通过分治法
        public String longestCommonPrefix(String[] strs, int start, int end) {
            if (start < end) {
                int mid = (end - start) / 2 + start;
                String lcpLeft = longestCommonPrefix(strs, start, mid);
                String lcpRight = longestCommonPrefix(strs, mid + 1, end);
                return commonPrefix(lcpLeft, lcpRight);
            }
            return strs[start];
        }

        private String commonPrefix(String lcpLeft, String lcpRight) {
            int end = 1;
            boolean first = false;
            while (end <= lcpLeft.length() && end <= lcpRight.length()) {
                if (lcpLeft.charAt(end - 1) == lcpRight.charAt(end - 1)) {
                    end++;
                    first = true;
                } else {
                    break;
                }
            }
            return first ? lcpLeft.substring(0, end - 1) : "";
        }
    }
    //3.通过二分法
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        int minLength = Integer.MAX_VALUE;
        for (String str : strs) {
            minLength = Math.min(minLength, str.length());
        }
        int low = 0, high = minLength;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (isCommonPrefix(strs, mid)) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return strs[0].substring(0, low);
    }

    public boolean isCommonPrefix(String[] strs, int length) {
        String str0 = strs[0].substring(0, length);
        int count = strs.length;
        for (int i = 1; i < count; i++) {
            String str = strs[i];
            for (int j = 0; j < length; j++) {
                if (str0.charAt(j) != str.charAt(j)) {
                    return false;
                }
            }
        }
        return true;
    }

//leetcode submit region end(Prohibit modification and deletion)

}